#include "StdAfx.h"
#include "Algorithm.h"

Algorithm::Algorithm(void)
{
	MAX_NUMBER_UNPODUCTIVE = 10;
}

Algorithm::~Algorithm(void)
{
}

std::size_t Algorithm::colorNumber(const Graph& graph) {
	std::set<std::size_t> colors;
	boost::graph_traits<Graph>::vertex_iterator vi, vi_end;
	for (boost::tie(vi, vi_end) = boost::vertices(graph); vi != vi_end; ++vi) {
		colors.insert(get(vertex_color, graph)[*vi]);
	}

	return colors.size();
}


bool Algorithm::containsColor(const Vertex& vert, std::size_t colorNum, const Graph& graph) {
	boost::graph_traits<Graph>::adjacency_iterator vi, viend;
	for (boost::tie(vi, viend) = adjacent_vertices(vert, graph); vi != viend; ++vi) {
		if (get(vertex_color, graph)[*vi] == colorNum) {
			return true;
		}
	}
	return false;
}


/**
* Initial coloring of graph, without any heuristics
*
* @param graph
* @return
*/
void Algorithm::initialColoring(Graph& graph) {
	std::vector<Vertex> vertices;
	boost::graph_traits<Graph>::vertex_iterator vi, vi_end;
	boost::tie(vi, vi_end) = boost::vertices(graph);
	vertices.insert(vertices.begin(),vi,vi_end);

	get(vertex_color, graph)[vertices.front()] = 1;

	for (std::size_t i = 1; i < vertices.size(); i++) {
		bool reColored = false;
		std::size_t color = 1;
		while (!reColored) {
			if (!containsColor(vertices.at(i), color, graph)) {
				get(vertex_color, graph)[vertices.at(i)] = color;
				reColored = true;
			}
			color++;
		}
	}
}


/**
* Generates array where each cell contains number of vertex with such color
* in graph (color number == cell position), if bySizes==true, else generates 
* array where each cell contains number of summary degree of
* class colored with color number N (N == color number == cell position)
*
* @param graph
* @return
*/
void Algorithm::fillUpVector(const Graph& graph, bool bySizes, std::vector<std::size_t>& gen_sizes) {
	std::size_t maxColorNumber = 0;
	boost::graph_traits<Graph>::vertex_iterator vi, vi_end;
	std::size_t tmp = 0;
	for (boost::tie(vi, vi_end) = boost::vertices(graph); vi != vi_end; ++vi) {
		tmp = boost::get(vertex_color, graph)[*vi];
		if (maxColorNumber < tmp) {
			maxColorNumber = tmp;
		}
	}

	gen_sizes.resize(maxColorNumber+1,0);

	if(bySizes){
		for (boost::tie(vi, vi_end) = boost::vertices(graph); vi != vi_end; ++vi) {
			gen_sizes.at(boost::get(vertex_color, graph)[*vi])++;
		}
	}else{
		for (boost::tie(vi, vi_end) = boost::vertices(graph); vi != vi_end; ++vi) {
			gen_sizes.at(boost::get(vertex_color, graph)[*vi]) +=
				boost::out_degree(*vi, graph);
		}
	}
}


/**
* Applies one iteration of algorithm to the graph.
*
* @param graph
*            graph for coloring (default: it is colored by color number 0)
* @param verList
*            ordered list of vertices to color
* @return
*/
void Algorithm::applyIteration(Graph& graph, const std::vector<Vertex>& verVector) {
	for (std::size_t i = 0; i < verVector.size(); i++) {
		Vertex vertex = verVector.at(i);
		bool reColored = false;
		std::size_t color = boost::get(vertex_color, graph)[vertex];
		std::size_t j = i + 1;

		while ((j < verVector.size() - 1) && color == boost::get(vertex_color, graph)[vertex]) {
			color = boost::get(vertex_color, graph)[ verVector.at(j)];
			j++;
		}

		while ((j < verVector.size()) && (!reColored)) {
			color = boost::get(vertex_color, graph)[ verVector.at(j)];
			if (!containsColor(vertex, color, graph)) {
				boost::get(vertex_color, graph)[vertex] = color;
				reColored = true;
			}
			j++;
		}
	}
}


/**
*	Binary predicat for sorting
*/
struct Algorithm::SortPred{

	SortPred(const Graph &GRAPH, bool PRED,std::vector<std::size_t>& GEN_SIZES): graph(GRAPH), pred(PRED), gen_sizes(GEN_SIZES){};
	bool operator () (Vertex v1, Vertex v2){
		if(pred){
			return gen_sizes.at(boost::get(vertex_color, graph)[v1]) < gen_sizes.at(boost::get(vertex_color, graph)[v2]);
		}else{
			return gen_sizes.at(boost::get(vertex_color, graph)[v1]) > gen_sizes.at(boost::get(vertex_color, graph)[v2]);
		}
	};

	const Graph &graph;
	bool pred;
	std::vector<std::size_t> gen_sizes;
};


void Algorithm::getVerticesOrderedBy(const Graph& graph, bool bySize, std::vector<Vertex>& vertices,std::vector<std::size_t>& gen_sizes) {
	gen_sizes.clear();
	fillUpVector(graph, bySize,gen_sizes);
	boost::graph_traits<Graph>::vertex_iterator vi, vi_end;
	boost::tie(vi, vi_end) = boost::vertices(graph);

	vertices.insert(vertices.begin(),vi,vi_end);

	std::sort(vertices.begin(),vertices.end(),SortPred(graph, bySize, gen_sizes));
}


void Algorithm::color(Graph& graph) {
	std::size_t numberOfRepeats = 0;
	std::size_t totalCounter = 0;
	std::size_t colorsNum = boost::num_vertices(graph);
	std::size_t numberOfProductiveIterations = 0;
	initialColoring(graph);
	std::size_t currentColorNum=colorNumber(graph);
	std::cout << "Initial: number of colors: " << currentColorNum << "\n";
	std::vector<Vertex> vertices(0);
	std::vector<std::size_t> gen_sizes(0);

	while (numberOfRepeats < MAX_NUMBER_UNPODUCTIVE) {
		//std::cout << totalCounter << " number of step\n";
		totalCounter++;
		vertices.clear();
		getVerticesOrderedBy(graph, numberOfRepeats % 2 == 0, vertices, gen_sizes);
		applyIteration(graph, vertices);
		currentColorNum = colorNumber(graph);
		//std::cout << "Number of colors: " << currentColorNum << "\n";
		if (colorsNum > currentColorNum) {
			numberOfRepeats = 0;
			colorsNum = currentColorNum;
			numberOfProductiveIterations++;
		} else {
			numberOfRepeats++;
		}
	}
	std::cout << "\nTotal iterations: " << totalCounter << "\nProductive iterations: " << numberOfProductiveIterations << "\n";
	std::cout << "Number of colors: " << currentColorNum << "\n";
}